Реферат з курсу "Введення в чисельні методи"
Тема: "ПРЯМІ МЕТОДИ РІШЕННЯ систему лінійних алгебраїчних рівнянь"
Зміст
1. Метод послідовних наближень
2. Метод Гауса-Зейделя
3. Метод звернення матриці
4. Тріангуляція матриці
5. Метод Халецького
6. Метод квадратного кореня
Література
1. Метод послідовних наближень
Найбільш поширеними методами стосовно до великих систем є ітераційні методи, які використовують розкладання матриці на суму матриць, та ітераційні методи, які використовують факторизації матриці, тобто представлення у вигляді твору матриць.
Проста ітерація: рівняння приводиться до вигляду , Наприклад, наступним чином:
,
де і містять довільну матрицю коефіцієнтів, по можливості бажано близьку до .
Якщо вибрати A = H + Q так, щоб у позитивно певної H легко знаходилася , Тоді вихідна система приводиться до наступного зручному для ітерацій увазі:
.
У цьому випадку, при симетричній матриці A і позитивно певної Q ітераційний процес сходиться при будь-якому початковому .
Якщо взяти H у вигляді діагональної матриці D = , В якій лише на головній діагоналі розташовані ненульові компоненти, то цей окремий випадок називається ітераційним методом Якобі.
2. Метод Гауса-Зейделя
Метод Гауса-Зейделя відрізняється тим, що вихідна матриця представляється сумою трьох матриць:
.
Підстановка в і нескладні еквівалентні перетворення приводять до наступної ітераційної процедури:
.
Розрізняють дві модифікації: одночасну підстановку і послідовну. У першій модифікації чергова підстановка виконується тоді, коли будуть обчислені всі компоненти нового вектора. У другій модифікації чергова підстановка вектора виконується в той момент, коли буде обчислено чергова компонента поточного вектора. У векторно-матричної формі запису послідовна підстановка методу Гауса-Зейделя виглядає так:
.
Друга форма вимагає істотно менше число ітерацій.
3. Метод звернення матриці
Еквівалентні перетворення матриці в твір більш простих, що приводять до рішення або полегшують його отримання, почнемо з розгляду методу звернення матриці. Так як в загальному виді рішення системи представляється через обернену матрицю у вигляді , То припустимо, що
,
тоді, помноживши праворуч рівність на матрицю A, отримаємо
.
Звідси можна зробити висновок, що матриці повинні послідовно зводити матрицю A до одиничною. Якщо перетворюючу матрицю вибрати так, щоб тільки один її стовпець відрізнявся від одиничних векторів-стовпчиків, тобто , То вектор-стовпець можна сформувати таким, щоб при множенні на поточну перетворені матрицю в останній i-тий стовпець перетворився на одиничний . Для цього беруть
і тоді .
Фактично це матричне твір перетворює всі компоненти проміжної матриці за формулами, що застосовуються в методі виключення Гауса. Особливість цього процесу полягає в тому, що діагональні елементи вихідної і всіх проміжних матриць не повинні бути нульовими.
Крім оберненої матриці, що дорівнює добутку всіх T-матриць, тепер можна отримувати і рішення рівнянь для будь-якого вектора у правій частині.
4. Тріангуляція матриці
Розкладання вихідної матриці на твір двох трикутних матриць (тріангуляція матриці) не є однозначною. Відповідно до цього є декілька різних методів, привабливих з тієї чи іншої сторони.
Сам спосіб формування рівнянь або формул для обчислення елементів трикутних матриць у різних методах практично однаковий: це метод невизначених коефіцієнтів.
Відмінності виникають на стадії вибору умов дозволу отриманих рівнянь. Нехай
,
де -
нижня трикутна матриця,
-
верхня трикутна матриця.
Виконуючи перемноження трикутних матриць і прирівнюючи отримувані елементи відповідних елементів вихідної матриці нескладно для k-того рядка і m-того стовпця записати
.
Отримана система складається з рівнянь і містить невідомих коефіцієнтів. За рахунок зайвих n невідомих існує свобода вибору, завдяки якій і є розмаїтість методів розкладання.
5. Метод Халецького
Якщо покласти , То розкладання і подальше рішення системи з двох векторно-матричних рівнянь з трикутними матрицями називається методом Халецького.
Елементи трикутних матриць L і U послідовно будуть обчислюватися за наступними формулами:
Якщо вихідна матриця симетрична, то від трикутних матриць можна вимагати, щоб вони були один до одного транспонований, тобто, наприклад, і так, що . У цьому випадку елементи трикутних матриць знаходяться в співвідношенні і, отже, число невідомих зменшується вдвічі. У результаті елементи трикутної матриці можуть обчислюватися за наступними формулами:
6. Метод квадратного кореня
Використання розкладання на взаємно транспонований трикутні матриці при вирішенні систем алгебраїчних рівнянь називається метод квадратного кореня.
Метод розкладу на транспонований трикутні матриці має модифікацію, яка полягає у виділенні в творі діагональної матриці D з елементами на діагоналі . Таким чином, для вихідної матриці, яка може бути і ермітової (симетричної і комплексно спряженої), розшукується добуток трьох матриць: .
Кожне km-те рівняння, визначається твором k-того вектора-рядка лівої трикутної матриці на діагональну матрицю, помножену на m-тий стовпець правою трикутної матриці, і має вигляд:
.
Для однозначного розкладання, зважаючи на комплексну спряженість симетричних елементів трикутних матриць, в першому рівнянні (i = 1), що має вид , Вважають . У цьому випадку
.
Аналогічно, відокремлюючи знак діагонального елемента діагональної матриці від його модуля, можна отримати формули для обчислення :
Література
1. Хеннер Є. К., Лапчик М. П., Рагуліна М. І. Чисельні методи. Вид-во: "Академія / Academia", 2004. - 384c.
2. Бахвалов І. В. Чисельні методи. БІНОМ, 2008. - 636c.
3. Формалей В. Д., Ревізніков Д. Л. Чисельні методи. Вид-во: Фізматліт ®, 2004. - 400c.
Тема: "ПРЯМІ МЕТОДИ РІШЕННЯ систему лінійних алгебраїчних рівнянь"
Зміст
1. Метод послідовних наближень
2. Метод Гауса-Зейделя
3. Метод звернення матриці
4. Тріангуляція матриці
5. Метод Халецького
6. Метод квадратного кореня
Література
1. Метод послідовних наближень
Найбільш поширеними методами стосовно до великих систем є ітераційні методи, які використовують розкладання матриці на суму матриць, та ітераційні методи, які використовують факторизації матриці, тобто представлення у вигляді твору матриць.
Проста ітерація: рівняння
де
Якщо вибрати A = H + Q так, щоб у позитивно певної H легко знаходилася
У цьому випадку, при симетричній матриці A і позитивно певної Q ітераційний процес сходиться при будь-якому початковому
Якщо взяти H у вигляді діагональної матриці D =
2. Метод Гауса-Зейделя
Метод Гауса-Зейделя відрізняється тим, що вихідна матриця представляється сумою трьох матриць:
Підстановка в
Розрізняють дві модифікації: одночасну підстановку і послідовну. У першій модифікації чергова підстановка виконується тоді, коли будуть обчислені всі компоненти нового вектора. У другій модифікації чергова підстановка вектора виконується в той момент, коли буде обчислено чергова компонента поточного вектора. У векторно-матричної формі запису послідовна підстановка методу Гауса-Зейделя виглядає так:
Друга форма вимагає істотно менше число ітерацій.
3. Метод звернення матриці
Еквівалентні перетворення матриці в твір більш простих, що приводять до рішення або полегшують його отримання, почнемо з розгляду методу звернення матриці. Так як в загальному виді рішення системи представляється через обернену матрицю у вигляді
тоді, помноживши праворуч рівність на матрицю A, отримаємо
Звідси можна зробити висновок, що матриці
Фактично це матричне твір перетворює всі компоненти проміжної матриці за формулами, що застосовуються в методі виключення Гауса. Особливість цього процесу полягає в тому, що діагональні елементи вихідної і всіх проміжних матриць не повинні бути нульовими.
Крім оберненої матриці, що дорівнює добутку всіх T-матриць, тепер можна отримувати і рішення рівнянь для будь-якого вектора у правій частині.
4. Тріангуляція матриці
Розкладання вихідної матриці на твір двох трикутних матриць (тріангуляція матриці) не є однозначною. Відповідно до цього є декілька різних методів, привабливих з тієї чи іншої сторони.
Сам спосіб формування рівнянь або формул для обчислення елементів трикутних матриць у різних методах практично однаковий: це метод невизначених коефіцієнтів.
Відмінності виникають на стадії вибору умов дозволу отриманих рівнянь. Нехай
де
нижня трикутна матриця,
верхня трикутна матриця.
Виконуючи перемноження трикутних матриць і прирівнюючи отримувані елементи відповідних елементів вихідної матриці нескладно для k-того рядка і m-того стовпця записати
Отримана система складається з
5. Метод Халецького
Якщо покласти
Елементи трикутних матриць L і U послідовно будуть обчислюватися за наступними формулами:
Якщо вихідна матриця симетрична, то від трикутних матриць можна вимагати, щоб вони були один до одного транспонований, тобто, наприклад,
6. Метод квадратного кореня
Використання розкладання на взаємно транспонований трикутні матриці при вирішенні систем алгебраїчних рівнянь називається метод квадратного кореня.
Метод розкладу на транспонований трикутні матриці має модифікацію, яка полягає у виділенні в творі діагональної матриці D з елементами на діагоналі
Кожне km-те рівняння, визначається твором k-того вектора-рядка лівої трикутної матриці на діагональну матрицю, помножену на m-тий стовпець правою трикутної матриці, і має вигляд:
Для однозначного розкладання, зважаючи на комплексну спряженість симетричних елементів трикутних матриць, в першому рівнянні (i = 1), що має вид
Аналогічно, відокремлюючи знак діагонального елемента діагональної матриці від його модуля, можна отримати формули для обчислення
Література
1. Хеннер Є. К., Лапчик М. П., Рагуліна М. І. Чисельні методи. Вид-во: "Академія / Academia", 2004. - 384c.
2. Бахвалов І. В. Чисельні методи. БІНОМ, 2008. - 636c.
3. Формалей В. Д., Ревізніков Д. Л. Чисельні методи. Вид-во: Фізматліт ®, 2004. - 400c.